package leetcode.剑指offer.后40;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/10 19:10
 * @description :https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
 */
public class 剑指_59_I_滑动窗口的最大值 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
    }

    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int len = nums.length;
            if (k == 0 || len == 0 || k > len)
                return new int[0];
            int[] dp = new int[len + 1 - k];
            PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
            for (int i = 0; i < k; i++) {
                queue.offer(nums[i]);
            }
            for (int i = k; i < len; i++) {
                dp[i - k] = queue.peek();
                queue.remove(nums[i - k]);
                queue.offer(nums[i]);
            }
            if (dp[dp.length - 1] == 0) {
                dp[dp.length - 1] = queue.peek();
            }
            return dp;
        }
    }
}
